package test;

import java.util.Arrays;

/**
 * TODO 快排
 *
 * @author david
 * @version 1.0
 * @date 2021/4/28 15:09
 */
public class Demo_QuickSort {
    public static void main(String[] args) {
        int[] b = {32,90,  1, 5, 4, 3, 6, 48, 32, 78};
        System.out.println(Arrays.toString(b));
        quickSort(b, 0, b.length - 1);
    }
    /**
     * 快速排序（挖坑法递归）
     *  @param array 待排序数组
     * @param low   左边界
     * @param high  右边界
     */
    private static void quickSort(int[] array, int low, int high) {
        if (array == null || array.length == 0) {
            return;
        }
        if (low >= high) {
            return;
        }
        int left = low;
        int right = high;
        int temp = array[left];//挖坑1：保存基准的值
        while (left < right) {
            while (left < right && temp <= array[right]) {
                right--;
            }
            array[left] = array[right]; //坑2：从后向前找到比基准小的元素，插入到基准位置坑1中
            System.out.println(Arrays.toString(array) );

            while (left < right && temp >= array[left]) {
                left++;
            }
            array[right] = array[left]; //坑3：从前往后找到比基准大的元素，放到刚才挖的坑2中
            System.out.println(Arrays.toString(array) );
        }
        array[left] = temp;// 基准值填补到坑3中，准备分治递归快排
        System.out.println("------"+Arrays.toString(array));
        System.out.println(left+"------"+right);

        quickSort(array, low, left - 1);//注意这里的是low不是left
        quickSort(array, left + 1, high);//注意这里是high 不是right
    }
}
